package leetcode;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

import org.junit.Test;

public class LongestConsecutiveSequence {
	public int longestConsecutive(int[] num) {
		if (num == null || num.length == 0)
			return 0;

		Map<Integer, Integer> nMap = new HashMap<Integer, Integer>();
		Map<Integer, Set<Integer>> clusters = new HashMap<Integer, Set<Integer>>();

		Integer cid = 0;
		for (int i = 0; i < num.length; ++i) {
			Integer n = num[i];

			if (nMap.containsKey(n)) {
				continue;
				// clusters.get(nMap.get(n)).add(n);
			} else {
				Integer pcid = nMap.get(n - 1);
				Integer ncid = nMap.get(n + 1);

				if (pcid == null && ncid == null) {
					nMap.put(n, cid);
					Set<Integer> nset = new HashSet<Integer>();
					nset.add(n);
					clusters.put(cid, nset);

					++cid;
				} else if (pcid != null && ncid != null) {
					nMap.put(n, pcid);
					for (Integer nn : clusters.get(ncid)) {
						nMap.put(nn, pcid);
					}

					Set<Integer> set = clusters.get(pcid);
					set.add(n);
					set.addAll(clusters.get(ncid));
					clusters.remove(ncid);
				} else {
					Integer ecid = pcid == null ? ncid : pcid;

					nMap.put(n, ecid);
					clusters.get(ecid).add(n);
				}
			}
		}

		int max = 0;

		for (Set<Integer> s : clusters.values())
			max = s.size() > max ? s.size() : max;

		return max;

	}

	@Test
	public void testResult() {
		LongestConsecutiveSequence lcs = new LongestConsecutiveSequence();

		int[] num = new int[] { -4, -1, 4, -5, 1, -6, 9, -6, 0, 2, 2, 7, 0, 9,
				-3, 8, 9, -2, -6, 5, 0, 3, 4, -2 };

		System.out.println(lcs.longestConsecutive(num));
	}
}
